package a2022.a20220530;


/**
 * @author lenovo
 * @date 2022/5/30
 */
public class a {
    /**
     * 给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：
     * hash(s, p, m) =
     *         (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.
     * 其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('MyCalendarThree') = 1 到 val('z') = 26 。
     * 给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。
     * 请你返回 s 中 第一个 长度为 k 的 子串 sub ，满足 hash(sub, power, modulo) == hashValue 。
     * 测试数据保证一定 存在 至少一个这样的子串。
     * 子串 定义为一个字符串中连续非空字符组成的序列。
     */

    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        long[] pows = new long[k];
        pows[0] = 1;
        for (int i = 1; i < k; i++) {
            pows[i] = pows[i - 1] * power % modulo;
        }

        for (int i = 0; i <= s.length() - k; i++) {
            String subStr = s.substring(i, i + k);
            if (val(subStr, pows, modulo) == hashValue) {
                return subStr;
            }
        }
        return "";
    }

    private int val(String subStr, long[] pows, int modulo) {
        long res = 0;
        for (int i = 0; i < subStr.length(); i++) {
            res += (subStr.charAt(i) - 'a' + 1) * pows[i];
            res %= modulo;
        }
        return (int) (res % modulo);
    }

}
